package com.shuang.backtracking13;

import java.util.*;

public class FindItinerary {
//    //方法一：used数组标记
//    class Solution {
//        //使用used数组标记 避免重复回到相同机场时的死循环
//        boolean[] used;
//        //存放结果的全局变量
//        List<String> res = new ArrayList<>();
//
//        public List<String> findItinerary(List<List<String>> tickets) {
//            //初始化used数组
//            used = new boolean[tickets.size()];
//            Arrays.fill(used, false);
//
//            //对tickets集合中 各个航班（起点到终点）集合中 终点进行排序 （要找排序靠前的行程）
//            //a, b分别代表tickets 集合中 每个航班的集合 取到航班集合中的终点元素 比较 按升序规则排序（从小到大）
//            Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
//
//            //起点一定是JFK开始 先将其存到结果中
//            res.add("JFK");
//
//            //处理 找到一条路线 是符合条件的行程直接返回 所以定义backTracking有返回值
//            backTracking(tickets);
//
//            return res;
//
//        }
//
//        private boolean backTracking(List<List<String>> tickets) {
//            //终止条件 res中存的结果等于 航班数加一时 证明到最后的结果了
//            if (res.size() == tickets.size() + 1) {
//                return true;
//            }
//
//            //for
//            for (int i = 0; i < tickets.size(); i++) {
//                // 利用used 避免死循环 tickets集合中的 航班集合的起点与 res中存的最后一个地点一致 则要处理这一行程地点
//                if (!used[i] && tickets.get(i).get(0).equals(res.get(res.size() - 1))) {
//                    //保存地点
//                    res.add(tickets.get(i).get(1));
//                    //标记该航班用过了 不可重复再用
//                    used[i] = true;
//
//                    //递归
//                    if (backTracking(tickets)) {
//                        return true;
//                    }
//
//                    //回溯
//                    res.remove(res.size() - 1);
//                    used[i] = false;
//                }
//            }
//
//            return false;
//        }
//    }

    //方法二：map集合
    class Solution {
        private Deque<String> res;
        private Map<String, Map<String, Integer>> map;

        private boolean backTracking(int ticketNum) {
            if (res.size() == ticketNum + 1) {
                return true;
            }
            String last = res.getLast();
            if (map.containsKey(last)) {//防止出现null
                for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
                    int count = target.getValue();
                    if (count > 0) {
                        res.add(target.getKey());
                        target.setValue(count - 1);
                        if (backTracking(ticketNum))
                            return true;
                        res.removeLast();
                        target.setValue(count);
                    }
                }
            }
            return false;
        }

        public List<String> findItinerary(List<List<String>> tickets) {
            map = new HashMap<String, Map<String, Integer>>();
            res = new LinkedList<>();
            for (List<String> t : tickets) {
                Map<String, Integer> temp;
                if (map.containsKey(t.get(0))) {
                    temp = map.get(t.get(0));
                    temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
                } else {
                    temp = new TreeMap<>();//升序Map
                    temp.put(t.get(1), 1);
                }
                map.put(t.get(0), temp);

            }
            res.add("JFK");
            backTracking(tickets.size());
            return new ArrayList<>(res);
        }
    }
}
